'''
给定一个无重复元素的数组和一个目标数，找出所有可以使数字和为目标数的组合（元素可以重复使用）
'''

def combination_sum(candidates, target):
    def backtrack(start, path, current_sum):
        # 基线条件：找到符合条件的组合
        if current_sum == target:
            result.append(path.copy())
            return
        # 剪枝：和超过目标值则停止
        if current_sum > target:
            return

        # 递归尝试每个可能的元素
        for i in range(start, len(candidates)):
            # 选择当前元素
            path.append(candidates[i])
            # 递归（可以重复使用当前元素，所以start不变）
            backtrack(i, path, current_sum + candidates[i])
            # 回溯：移除最后一个元素
            path.pop()

    result = []
    backtrack(0, [], 0)
    return result


# 测试
print(combination_sum([2, 3, 6, 7], 7))
# 输出: [[2,2,3], [7]]
print(combination_sum([2, 3, 5], 8))
# 输出: [[2,2,2,2], [2,3,3], [3,5]]

